#include "DynamicPlanning.h"

void test1() {
    DynamicPlanning DP;
    int n = 5;
    // int res = DP.ClimbStairsDP(n);
    int res = DP.ClimbStairsDPComp(n);
    std::cout << "爬" << n << "阶台阶，共有" << res << "种方案" << std::endl;
}

void test2() {
    DynamicPlanning DP;
    std::vector<int> cost{0,5,2,6,2};
    int res = DP.minCostClimbStairsDP(cost);
    std::cout << "爬" << cost.size() - 1 << "阶台阶，最小代价是" << res << std::endl;
}

void test3() {
    DynamicPlanning DP;
    std::vector<std::vector<int>> grid = {{1,3,1,5},{2,2,4,2},{5,3,2,1},{4,3,5,2}};
    int res = DP.minPathSumDFS(grid,3,3);
    std::cout << "最小路径和是" << res << std::endl;
}

void test4() {
    DynamicPlanning DP;
    std::vector<std::vector<int>> grid = {{1,3,1,5},{2,2,4,2},{5,3,2,1},{4,3,5,2}};
    std::vector<std::vector<int>> mem(4,std::vector<int>(4,-1));
    int res = DP.minPathSumDFSMem(grid,mem,3,3);
    std::cout << "最小路径和是" << res << std::endl;
}

void test5() {
    DynamicPlanning DP;
    std::vector<std::vector<int>> grid = {{1,3,1,5},{2,2,4,2},{5,3,2,1},{4,3,5,2}};
    int res = DP.minPathSumDPComp(grid);
    std::cout << "最小路径和是" << res << std::endl;
}

void test6() {
    DynamicPlanning DP;
    std::vector<int> wgt = {1,2,3};
    std::vector<int> val = {5,11,15};
    int res = DP.knapackDFS(wgt,val,3,3);
    std::cout << "暴力搜索-背包放入物品的最大价值是：" << res << std::endl;
}

void test7() {
    DynamicPlanning DP;
    std::vector<int> wgt = {1,2,3};
    std::vector<int> val = {5,11,15};
    std::vector<std::vector<int>> mem(4,std::vector<int>(4,-1));
    int res = DP.knapackDFSMem(wgt,val,mem,3,3);
    std::cout << "记忆化搜索-背包放入物品的最大价值是：" << res << std::endl;
}

void test8() {
    DynamicPlanning DP;
    std::vector<int> wgt = {1,2,3};
    std::vector<int> val = {5,11,15};
    int res = DP.knapackDP(wgt,val,3);
    std::cout << "动态规划-背包放入物品的最大价值是：" << res << std::endl;
}

void test9() {
    DynamicPlanning DP;
    std::vector<int> wgt = {1,2,3};
    std::vector<int> val = {5,11,15};
    int res = DP.knapackDPComp(wgt,val,3);
    std::cout << "空间优化-背包放入物品的最大价值是：" << res << std::endl;
}

void test10() {
    DynamicPlanning DP;
    std::vector<int> wgt = {1,2,3};
    std::vector<int> val = {5,11,15};
    int res = DP.unboundedknapackDP(wgt,val,3);
    std::cout << "完全背包动态规划-背包放入物品的最大价值是：" << res << std::endl;
}

void test11() {
    DynamicPlanning DP;
    std::vector<int> wgt = {1,2,3};
    std::vector<int> val = {5,11,15};
    int res = DP.unboundedknapackDPComp(wgt,val,4);
    std::cout << "完全背包动态规划空间优化-背包放入物品的最大价值是：" << res << std::endl;
}

void test12() {
    DynamicPlanning DP;
    std::vector<int> coins = {1,2,5};
    int amt = 4;
    int res = DP.CoinsChangeDP(coins,amt);
    std::cout << "零钱兑换动态规划-凑出数额=" << amt << "的硬币最小数量是: " << res << std::endl;
}

void test13() {
    DynamicPlanning DP;
    std::vector<int> coins = {1,2,5};
    int amt = 4;
    int res = DP.CoinsChangeDPComp(coins,amt);
    std::cout << "零钱兑换空间优化-凑出数额=" << amt << "的硬币最小数量是: " << res << std::endl;
}

void test14() {
    DynamicPlanning DP;
    std::vector<int> coins = {1,2,5};
    int amt = 5;
    int res = DP.CoinsChangeIIDP(coins,amt);
    std::cout << "零钱兑换II动态规划-凑出数额=" << amt << "的硬币组合数量是: " << res << std::endl;
}

void test15() {
    DynamicPlanning DP;
    std::vector<int> coins = {1,2,5};
    int amt = 5;
    int res = DP.CoinsChangeIIDPComp(coins,amt);
    std::cout << "零钱兑换II空间优化-凑出数额=" << amt << "的硬币组合数量是: " << res << std::endl;
}

void test16() {
    DynamicPlanning DP;
    std::string s = "bag";
    std::string t = "pack";
    int res = DP.EditDiatance(s,t);
    std::cout << "编辑距离问题-动态规划，最小编辑步数: " << res << std::endl;
}

void test17() {
    DynamicPlanning DP;
    std::string s = "bag";
    std::string t = "pack";
    int res = DP.EditDiatanceComp(s,t);
    std::cout << "编辑距离问题-空间优化，最小编辑步数: " << res << std::endl;
}



int main() {
    std::cout << "动态规划" << std::endl;
    test17();
    return 0;
}